package main

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

/**
 *
 * @param root TreeNode类 the root of binary tree
 * @return int整型二维数组
 */
func threeOrders(root *TreeNode) [][]int {
	// write code here
	if root == nil {
		return [][]int{{}, {}, {}}
	}
	l := threeOrders(root.Left)
	r := threeOrders(root.Right)
	return [][]int{merge2(root.Val, l[0], r[0]), merge1(l[1], root.Val, r[1]), merge3(l[2], r[2], root.Val)}
}

func merge1(l []int, m int, r []int) []int {
	l = append(l, m)
	return append(l, r...)
}
func merge2(m int, l []int, r []int) []int {
	l = append([]int{m}, l...)
	return append(l, r...)
}
func merge3(l []int, r []int, m int) []int {
	l = append(l, r...)
	return append(l, m)
}
